1. Field of the Invention
The present invention generally relates to the art of electronic data transmission, and more specifically to a method and apparatus for convolutional interleaving and de-interleaving of data for correcting bursts of errors in transmitted data.
2. Description of the Related Art
In many applications of communications technology, interleaving is used in combination with encoding for error correction. One technique, which is applicable to some types of burst-error communications channels, is to insert an interleaver between the channel encoder at the transmitting end and the channel. The interleaver redistributes the data bits or symbols being transmitted over the channel so that the symbols are mutually separated by substantially more than the length of a "typical" burst of errors.
Interleaving effectively makes the channel appear like a random-error channel to a decoder at the receiving end. For some high frequency channels, this technique can improve the performance by one to three orders of magnitude.
Improvements in digital communications technology have increased the demands on Forward Error Correction (FEC) techniques. For example, compressed video systems require an extremely low Bit-Error Rate (BER) on the order of 1e-12 (one error per 10.sup.12 bits of data). Conventional FEC techniques require high transmitter power and large data overhead to achieve these low BERs. The concatenation and interleaving of several FEC techniques reduces the power and bandwidth expansion required by a single error correction code to obtain the same low error rate.
FIG. 1 illustrates a basic interleaved/concatenated FEC communications system 10, comprising a transmitter 12 and a receiver 14 that are connected by a communications channel 16. The transmitter 12 includes a first or outer encoder 18 that encodes input data using a Reed-Solomon code or other suitable code, and a second or inner encoder 20 that further encodes the data using a Convolutional or Hamming code. The receiver 14 includes an inner decoder 22 and an outer decoder 24 that are conjugate to the encoders 18 and 20 respectively.
The "rate" R of the code is defined as the reciprocal of the bandwidth expansion. For instance an R=1/2 code doubles the bandwidth or data rate in the transmission channel. If two individual codes are used, the overall rate is the product of the two codes.
Another measure of the effectiveness of an error correction technique is the Signal to Noise Ratio (SNR) that is required to obtain the necessary BER at the output of the outer decoder 24. A low SNR corresponds to a low power requirement for the transmitter 12, and thereby lower cost. The best codes have a high rate R and a low SNR for a given BER.
The inner codes that are selected usually perform well at low SNR (high channel BER). They can easily push the BER from the range of 1e-2 to the range of 1e-4. However, it is difficult for the inner code alone to reach the 1e-12 BER system requirement.
The outer codes, on the other hand, can easily push the BER from 1e-4 to 1e-12, but usually will not work at low SNR. Hence, the concatenated scheme is highly desirable for systems such as Direct Broadcast Satellite (DBS), and create only a moderate bandwidth expansion.
The above analysis applies only to the assumption that the errors are uncorrelated or randomly distributed. In practical applications, however, the output of the inner decoder 22 tends to be very bursty. This causes the error pattern to be highly correlated and concentrated only in a small portion of the bit stream. Under these conditions, the outer decoder 24 will not perform effectively. In order to alleviate this problem, an interleaving/de-interleaving function is added to the system 10.
As further illustrated in FIG. 2, the system 10 further comprises an interleaver 26 connected between the encoders 18 and 20 and a de-interleaver 28 connected between the decoders 22 and 24. The interleaver 26 reorders a sequence of symbols or data bits in a one-to-one deterministic manner. The de-interleaver 28 restores the reordered sequence to its original ordering.
More specifically, the de-interleaver 28 breaks the bursts of errors from the inner decoder 22 into pieces and spreads the errors into several different outer code words. This eases the burden on the outer decoder 24, which is able to clean up the remaining errors successfully.
The reduction of required power by one-half for the concatenated code can result in a significantly lowered cost in an application such as Direct Broadcast Satellite (DBS) video systems. The reduction in required power can be manifested in cheaper transmitters and receivers.
A periodic interleaver is an interleaver for which the interleaving permutation is a periodic function of time. Two basic types of periodic interleavers are known in the prior art; block interleavers and convolutional interleavers.
A block interleaver writes symbols into an array by columns, and reads them out by rows. The de-interleaver writes the received symbols by rows, and reads them out by columns, thus, reversing the interleaving operation. The interleaving/de-interleaving permutation is performed on block boundaries.
Assuming a block length (number of columns) of N and an interleave depth (number of rows) of B, the number of memory locations required to implement a block interleaver is 2.times.N.times.B, since all of the symbols must be written into memory before they can be read out.
A convolutional Interleaver performs a periodic permutation over a continuous semi-infinite sequence of symbols. This group of interleavers results in an easier synchronization scheme and requires a smaller RAM configuration while achieving the same performance.
A convolutional helical interleaver achieves the same performance as the block interleaver, but requires only half as much memory for implementation. In the interleaver operation, reading is done by rows and writing is done by columns. However, the write location is forced to equal the read location after each N symbols. This configuration enables the memory requirement to be reduced to N.times.B.
Optimal implementations for convolutional periodic interleavers are proposed in an article entitled "Realization of Optimum Interleavers", by John Ramsey, in IEEE Transactions on Information Theory, May 1970, pp. 338-345, and also in an article entitled "Burst-Correcting Codes for the Classic Bursty Channel", by G. David Forney, in IEEE Transactions on Communications Technology, Vol. COM-19, No. 5, October 1971, pp. 772-780.
These solutions, although different, are optimal and reach the minimum bound of required memory and total end to end delay. They both reduce the required memory to about (N.times.B)/2 at the transmitter and at the receiver, which is half the memory required for a helical interleaver, and about 25% of the memory required for a block interleaver.
Forney's optimal convolutional interleaver configuration is illustrated in FIG. 2. An interleaver 30 at a transmitting end of a communications channel 32 comprises a plurality of shift register segments 34, 36, 38 and 40 having different lengths. A de-interleaver 42 at a receiving end of the channel 32 comprises a plurality of shift register segments 44, 46, 48 and 50 having the same lengths as the segments 40, 38, 36 and 34 of the interleaver 30 respectively.
The length C.sub.K (the number of stages in the shift registers) of each segment 34, 36, 38 and 40 is selected in accordance with a parameter M=N/B and a segment number K such that C.sub.K =K.times.M=K.times.(N/B). There are B segments, for which K is K.sub.0 to K.sub.(B-1) respectively.
For the first segment 34, K=0, and the length C=0 (the first segment 34 is a direct connection). For the second segment 36, K=1, and C=M. For the last segment 40, K=B-1, and C=(B-1).times.M.
The interleaver 30 further comprises an input switch 52 and an output switch 54, whereas the de-interleaver 42 comprises an input switch 56 and an output switch 58. The interleaver 30 is operated by using the switches 52 and 54 to sequentially select the segments 34, 36, 38 and 40.
To select the segment 34, for example, the switches 52 and 54 are moved to the illustrated positions such that the input of the segment 34 is connected to the input of an encoder such as illustrated at 18 in FIG. 1, and the switch 54 is connected between the output of the segment 34 and the channel 32.
After a segment 34, 36, 38 or 40 is selected, the oldest symbol or data bit in the segment is read out from the right end of the respective shift register, a new symbol is written into the left end of the shift register, and all other symbols are shifted to the right. The switches 52 and 54 are then operated to select the next segment. On the de-interleaver side the reverse operation is performed using the switches 56 and 58, and the original order is restored.
Although providing effective interleaving/de-interleaving operation with reduced memory requirements, Forney's convolutional interleaver configuration as described in the above referenced article suffers from several disadvantages.
1. The shift register configuration requires a disproportionally large area when implemented on a semiconductor chip. PA1 2. The hard-wired architecture constrains the user to a pre-defined set of system parameters. PA1 3. B must divide N. For this reason, some (B,N) pairs are not allowed. PA1 1. The interleaving depth B can be changed according to the system requirements. PA1 2. The block length N is programmable to any number. PA1 3. A single input signal determines if the apparatus will function as an interleaver on the encoder side, or as a de-interleaver on the decoder side. PA1 4. Special relationships between N and B are not required. The method described in the above referenced article to Ramsey and the helical interleaving scheme constrain the system to relative primeness relations between N and B. In the method described in the above referenced article to Forney, B must divide N. The present method has no such constraints.